package com.example.myapplication9.week8.jsjf;


import com.example.myapplication9.week8.jsjf.exceptions.EmptyCollectionException;

public class ArrayHeap1<T> extends ArrayBinaryTree<T>
{

    public static void main(String[] args) {
        ArrayHeap1<Integer> temp=new ArrayHeap1<Integer>();
        int[]data={36,30,18,40,32,45,22,50};

        //将数组中的元素添加到大顶堆中
        for (int i = 0; i < data.length; i++)
            temp.addElement(data[i]);


                        //层序输出输出构造好的大顶堆序列
        String result="";

                        System.out.println("大顶堆层序遍历：");
                        System.out.println(temp.toString());

                        //输出每轮排序的结果（数组的结果）
                        System.out.println("堆的层序遍历结果:");
                        for (int a=0;a<data.length;a++)
                        {
                            data[a]=temp.removeMax();
                            String result1="";
                            for (int b=0;b<=a;b++){
                                result1+=data[b]+" ";
                            }


                                result1+=temp.toString()+" ";

                            System.out.println("第"+(a+1)+"次："+result1);

                        }

                        String result2="";
                        for (int a=0;a<data.length;a++){
                            result2+=data[a]+" ";
                        }
                        System.out.println("排序结果："+result2);
                    }


                    public ArrayHeap1()
    {
        super();
    }

    public void addElement(T obj)
    {
        if (count == tree.length)
            expandCapacity();

        tree[count] = obj;
        count++;
        modCount++;

        if (count > 1)
            heapifyAdd();
    }


    private void heapifyAdd()
    {
        T temp;
        int next = count - 1;

        temp = tree[next];

        while ((next != 0) &&
                (((Comparable)temp).compareTo(tree[(next-1)/2]) > 0))
        {

            tree[next] = tree[(next-1)/2];
            next = (next-1)/2;
        }

        tree[next] = temp;
    }


    public T removeMax() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");

        T maxElement = tree[0];
        tree[0] = tree[count-1];
        heapifyRemove();
        count--;
        modCount--;
        tree[count] =null;

        return maxElement;
    }

    private void heapifyRemove()
    {
        T temp;
        int node = 0;
        int left = 1;
        int right = 2;
        int next;

        if ((tree[left] == null) && (tree[right] == null))
            next = count;
        else if (tree[right] == null)
            next = left;
        else if (((Comparable)tree[left]).compareTo(tree[right]) > 0)
            next = left;
        else
            next = right;
        temp = tree[node];

        while ((next < count) &&
                (((Comparable)tree[next]).compareTo(temp) > 0))
        {
            tree[node] = tree[next];

            node = next;
            left = 2 * node + 1;
            right = 2 * (node + 1);
            if ((tree[left] == null) && (tree[right] == null))
                next = count;
            else if (tree[right] == null)
                next = left;
            else if (((Comparable)tree[left]).compareTo(tree[right]) > 0)
                next = left;
            else
                next = right;
        }
        tree[node] = temp;
    }

    public T findMax() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");

        return tree[0];
    }
}
